package mine.code.question.动态规划;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入:
 * A: [1,2,3,2,1]
 * B: [3,2,1,4,7]
 * 输出: 3
 * 解释:
 * 长度最长的公共子数组是 [3, 2, 1]。
 * 说明:
 * <p>
 * 1 <= len(A), len(B) <= 1000
 * 0 <= A[i], B[i] < 100
 *
 * @author caijinnan
 * @date 2020/6/8 11:35
 */
public class 最长重复子数组 {

    @Test
    public void run() {
//        int[] A = {70, 39, 25, 40, 7};
//        int[] B = {52, 20, 67, 5, 31};
        int[] A = {1,2,3,2,1};
        int[] B = {3,2,1,4,7};
        System.out.println(findLength(A, B));
    }

    //dp[i][j] = dp[i-1][j-1]+checkNum
    public int findLength(int[] A, int[] B) {
        if (A.length == 0 || B.length == 0) {
            return 0;
        }
        int[][] dp = new int[A.length][B.length];
        //初始化
        for (int i = 0; i < A.length; i++) {
            dp[i][0] = A[i] == B[0] ? 1 : 0;
        }
        for (int i = 0; i < B.length; i++) {
            dp[0][i] = A[0] == B[i] ? 1 : 0;
        }

        int maxLength = 0;
        for (int i = 1; i < A.length; i++) {
            for (int j = 1; j < B.length; j++) {
                if (A[i] == B[j]) {
                    int checkNum = 1;
                    int lastNum = dp[i - 1][j - 1];
                    for (int k = i - lastNum, l = j - lastNum; k <= i; k++, l++) {
                        if (A[k] != B[l]) {
                            checkNum = 0;
                            break;
                        }
                    }
                    dp[i][j] = dp[i - 1][j - 1] + checkNum;
                } else {
                    dp[i][j] = dp[i - 1][j - 1] ;
                }
                maxLength = Math.max(dp[i][j], maxLength);
            }
        }
        for (int[] ints : dp) {
            System.out.println(Arrays.toString(ints));
        }
        return maxLength;
    }
}